# !/usr/bin/env python
# -*- coding: utf-8 -*-
"""
@Time        : 2020/12/30 15:20
@Author      : Albert Darren
@Contact     : 2563491540@qq.com
@File        : polynomial_evaluation.py
@Version     : Version 1.0.0
@Description : TODO 实现秦九韶算法
@Created By  : PyCharm
"""
import numpy as np
from sympy.abc import x


def polynomial(coefficient_array: np.ndarray, is_ascending_order: bool = False):
    """
    构造指定系数的多项式
    :param coefficient_array: 多项式系数数组
    :param is_ascending_order: 多项式排列顺序
    :return: 多项式
    """
    degree = coefficient_array.shape[0]
    if is_ascending_order:
        coefficient_array = coefficient_array[::-1]
    # default,descending order arrangement
    p_x = coefficient_array[-1]
    for i in range(degree - 1, 0, -1):
        p_x += coefficient_array[degree - i - 1] * pow(x, i)
    return p_x


def qin_jiu_shao(coefficient_array: np.ndarray, value, is_ascending_order: bool = False):
    """
    多项式求值的秦九韶算法,即Horner算法
    :param coefficient_array: 多项式系数数组
    :param value: 自变量的值
    :param is_ascending_order: 多项式排列顺序
    :return: the value of polynomial
    example:
    2*x**4 - 3*x**2 + 3*x - 4=((((2x+0)x-3)x+3)x-4)
    3*x**5 - 2*x**3 + x + 7=(((((3x+0)x-2)x+0)x+1)x+7)
    """
    if is_ascending_order:
        coefficient_array = coefficient_array[::-1]
    degree = coefficient_array.shape[0]
    b = coefficient_array[0]
    for i in range(1, degree):
        b = b * value + coefficient_array[i]
    return b


if __name__ == '__main__':
    # 测试成功，来源详见李庆扬数值分析第5版P14，e.g.11
    # 降幂排列
    coefficient0 = np.array([2, 0, -3, 3, -4])
    print(polynomial(coefficient0))
    print(qin_jiu_shao(coefficient0, -2))
    # 升幂排列
    coefficient1 = np.array([-4, 3, -3, 0, 2])
    print(polynomial(coefficient1, is_ascending_order=True))
    print(qin_jiu_shao(coefficient1, -2, is_ascending_order=True))
    # 测试成功，来源详见李庆扬数值分析第5版P20，e.x.14
    # 降幂排列
    coefficient2 = np.array([3, 0, -2, 0, 1, 7])
    print(polynomial(coefficient2))
    print(qin_jiu_shao(coefficient2, 3))
    # 升幂排列
    coefficient3 = np.array([7, 1, 0, -2, 0, 3])
    print(polynomial(coefficient3, is_ascending_order=True))
    print(qin_jiu_shao(coefficient3, 3, is_ascending_order=True))
